def floyd(dis, path):
    len_matrix = len(dis)
    for temp in range(len_matrix):
        for row in range(len_matrix):
            for col in range(len_matrix):
                if row == col:
                    dis[row][col] = 0
                    path[row][col] = row
                else:
                    if dis[row][temp] + dis[temp][col] < dis[row][col]:
                        dis[row][col] = dis[row][temp] + dis[temp][col]
                        path[row][col] = path[row][temp]

def store(dis, path):
    len_matrix = len(path)
    with open("Path Matrix", "w") as f1:
        for i in range(len_matrix):
            for j in range(len_matrix):
                f1.write(str(path[i][j]))
                f1.write(' ')
            f1.write('\n')
    with open("Distance Matrix", "w") as f1:
        for i in range(len_matrix):
            for j in range(len_matrix):
                f1.write(str(dis[i][j]))
                f1.write(' ')
            f1.write('\n')

def get(matrix):
    with open(matrix) as f1:
        list = f1.read()
        lines = list.split('\n')[:-1]
        mart = []
        for line in lines:
            m = line.split(' ')[:-1]
            mart.append([int(i) for i in m])
        return mart

def print_Martrix(mart):
    for itens in mart:
        print("")
        for item in itens:
            print("%s\t" % item, end = "")
    print("")

def path_Print(dis, path):
    len_matrix = len(path)
    for row in range(len_matrix):
        for col in range(len_matrix):
            if row != col:
                print("v" + str(row + 1) + "---v" + str(col+1) + "  Weight: " + str(dis[row][col]) + "  Path: v" + str(row + 1), end = '')
                temp = path[row][col]
                while temp != col:
                    print("-->v" + str(temp + 1), end = '')
                    temp = path[temp][col]
                print("-->v" + str(col + 1), end = '')
                print("")
        print("")


if __name__ == '__main__':
    INF = float("inf")
    with open("matrix") as f1:
        n = int(f1.readline()[:-1])
        dis = [[INF] * n for i in range(n)]
        path = [list(range(n)) for i in range(n)]
        edge = f1.readline()
        while edge:
            b, e, w = [int(i) for i in edge.split()]
            dis[b - 1][e - 1] = w
            edge = f1.readline()
    print("初始邻接矩阵:")
    print_Martrix(dis)
    floyd(dis, path)
    # 存储矩阵
    # store(dis, path)
    path_Print(dis, path)
    # with open("Co-ordinate", "r+") as f1:
    #     list = f1.read()
    #     lines = list.split('\n')[:-1]
    #     mart = []
    #     for line in lines:
    #         m = line[line.find('(') + 1:line.find(',') + 1] + line[line.find(',') + 2:line.find(')')]
    #         f1.write(m)
    #         f1.write('\n')


